//
// Created by id on 2025/10/9.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct myChar {
    char ch[MAX_SIZE];  ///< 字符数组
    int length;         ///< 当前长度
} myChar;

void getNextBase1(myChar *pattern, int next[]) {
    int i = 1;
    int j = 0;
    next[1] = 0;
    while ( i < pattern->length ) {
        if (j == 0 || pattern->ch[i] == pattern->ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
  }

void getNextBase0(myChar *pattern, int next[]) {
    int i = 0;
    int j = -1;
    next[0] = -1;
    while ( i < pattern->length -1) {
        if ( j== -1 || pattern->ch[i] == pattern->ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int indexKMPBase1(myChar *text, myChar *pattern, int next[]) {
    if (pattern == NULL || pattern->length == 0) return -1;
    if (pattern->length > text->length) return -1;
    int i = 1;
    int j = 1;
    getNextBase1(pattern, next);

    while ( i <= text->length && j <= pattern->length ) {
        if (j ==0 || text->ch[i] == pattern->ch[j]) {
            i ++;
            j ++;
        } else {
            j = next[j];
        }
    }
    return (j > pattern->length) ? (i - pattern->length) : -1;
}

int indexKMPBase0(myChar *text, myChar *pattern, int next[]) {
    if (pattern == NULL || pattern->length == 0) return -1;
    if (pattern->length > text->length) return -1;
    int i = 0;
    int j = 0;
    getNextBase0(pattern, next);
    while (i < text->length && j < pattern->length) {
        if (j == -1 || text->ch[i] == pattern->ch[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }

    return (j == pattern->length) ? (i - pattern->length) : -1;

}


int main() {
    // ---------------- 教材版本测试 ----------------
    myChar text1;  // abcababc
    text1.ch[1] = 'a';
    text1.ch[2] = 'b';
    text1.ch[3] = 'c';
    text1.ch[4] = 'a';
    text1.ch[5] = 'b';
    text1.ch[6] = 'a';
    text1.ch[7] = 'b';
    text1.ch[8] = 'c';
    text1.length = 8;

    myChar pattern1;  //ababc
    pattern1.ch[1] = 'a';
    pattern1.ch[2] = 'b';
    pattern1.ch[3] = 'a';
    pattern1.ch[4] = 'b';
    pattern1.ch[5] = 'c';
    pattern1.length = 5;

    int next1[pattern1.length + 1];
    int pos1 = indexKMPBase1(&text1, &pattern1, next1);
    if (pos1 != -1) {
        printf("Pattern found at position %d (1-based)\n", pos1);
    } else {
        printf("Pattern not found (1-based)\n");
    }


    // ---------------- 实际版本测试 ----------------
    myChar text0 = {"abcababc", 8};
    myChar pattern0 = {"ababc", 5};
    int next0[pattern0.length];

    int pos0 = indexKMPBase0(&text0, &pattern0, next0);
    if (pos0 != -1) {
        printf("Pattern found at position %d (0-based)\n", pos0);
    } else {
        printf("Pattern not found (0-based)\n");
    }

}
